
/*
回溯--全排列2
连接：https://leetcode.cn/problems/permutations-ii/
题目：47. 全排列 II




画出决策树：
设计代码：
    全局变量：
        int ret[][];保存结果
        int path[];选择路径
        bool check[];记录下标对应的数是否被选用
    dfs函数：
       仅需关心某一个节点在干什么
    细节问题
        回溯：干掉path最后一个元素；修改check数组
        减枝:两种情况下会减枝
            1.本次选择的数字已经在其他位置选过了，那么就不能选了，例如对于数组{1,1,2}第一次选 1_,_。第二次选的时候1,1(第一个1)_就不能这么选
            2.本次选择的数字和上一次选择的数字值是一样的，并且选择位置相同，那么就不能选了列入选了1（第一个1）,_,_，就不能选1（第二个1）_,_
        递归出口：遇到叶子节点，添加结果


*/
class Solution {
public:
    bool check[9]={false};
    vector<vector<int>> ret;
    vector<int> path;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int pos=0;
        dfs(nums,pos);//pos代表选的数字个数
        return ret;
    }
    void dfs(vector<int>& nums,int pos)
    {
        if(pos==nums.size())
        {
            ret.push_back(path);
            return ;
        }
        //什么时候去递归调用
        for(int i=0;i<nums.size();i++)
        {
            //可以选择的分支：当前数字没被选过，并且，第一次选择、或者选择的数字不和上一次选择的相同、或者相同但是不在同一个位置选择
            if(check[i]==false && (i==0|| (nums[i]!=nums[i-1] || check[i-1]==true)))
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums,pos+1);
                check[i] = false;
                path.pop_back();
            }
            
        }
        
    }
};

//不可以选择的分支:当前数字备选过了，或者，不是第一次选，前面的数字值和当前数字值相同而且还是在同一个位置选择
//if(check[i]==true || (i!=0&&(nums[i]==nums[i-1] && check[i-1]==false)))
 void dfs(vector<int>& nums,int pos)
    {
        if(pos==nums.size())
        {
            ret.push_back(path);
            return ;
        }
        //什么时候去递归调用
        for(int i=0;i<nums.size();i++)
        {
            if(check[i]==true || (i!=0&&(nums[i]==nums[i-1] && check[i-1]==false)))
            {
               continue;
            }
             path.push_back(nums[i]);
                check[i] = true;
                dfs(nums,pos+1);
                check[i] = false;
                path.pop_back();
        }
        
    }